package com.ideas.impl.mianshi;

import java.util.Arrays;

/**
 * @Author lijian.wu
 * @Date 2024/4/17 21:06
 * 有一个包含N个整数的数组，请编写一个算法，找到其中的两个元素，使它们之差最小。时间复杂度必须为O(n)
 */
public class MinDiff {

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 5, 9, 2, 6, 8, 7};
        int minDiff = findMinDiff(arr);
        System.out.println("最小差为：" + minDiff);
    }

    /**
     * 使用桶排序来实现时间复杂度为O(n)的算法。
     * 1、先扫描一遍数组，找到数组中的最大值和最小值。
     * 2、根据最大值和最小值计算桶的个数和桶的宽度，桶的个数为(maxValue - minValue + 1)，桶的宽度为1。
     * 3、将每个元素放到对应的桶中，接着对每个桶执行排序
     * 4、从第一个桶开始，计算该桶内的最大值和下一个非空桶的最小值之差，记录最小值。
     * 5、返回最小值即为所求。
     * @param arr
     * @return
     */
    private static int findMinDiff(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return -1;
        }
        // 找到最大值和最小值
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if(arr[i] < min){
                min = arr[i];
            }
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int bucketWidth = 1;
        int bucketCount = max - min + 1;

        // 初始化桶
        int[][] buckets = new int[bucketCount][n];
        //储存每个桶中元素的个数
        int[] bucketSizes = new int[bucketCount];

        // 将元素放到对应的桶中
        for (int i = 0; i < n; i++) {
            int index = (arr[i] - min)/bucketWidth;
            //入桶，同时该桶元素数+1
            buckets[index][bucketSizes[index]++] = arr[i];
        }

        // 对每个桶进行排序
        for (int i = 0; i < bucketCount; i++) {
            if(bucketSizes[i] > 0){
                Arrays.sort(buckets[i],0,bucketSizes[i]);
            }
        }

        //计算相邻桶的最小差值
        int minDiff = Integer.MAX_VALUE;
        int preMax = buckets[0][bucketSizes[0]-1];
        for (int i = 1; i < bucketCount; i++) {
            if (bucketSizes[i] == 0) {
                continue;
            }
            //当前桶的最小值
            int currMin = buckets[i][0];
            if(currMin - preMax < minDiff){
                minDiff = currMin - preMax;
            }
            preMax = buckets[i][bucketSizes[i]-1];
        }
        return minDiff;
    }

}
